/**
 * @(#)SkipList.java, 9月 01, 2021.
 * <p>
 * Copyright 2021 fenbi.com. All rights reserved.
 * FENBI.COM PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package com.wxweven.algorithm.list;

import java.util.Random;

/**
 * @author wxweven
 */
public class SkipList {

    private static final double PROMOTE_RATE = 0.5;

    private Node head, tail;
    private int height;

    public SkipList() {
        head = new Node(Integer.MIN_VALUE);
        tail = new Node(Integer.MAX_VALUE);

        head.right = tail;
        tail.left = head;
    }

    private static class Node {
        private int data;
        private Node right, left, up, down;

        public Node(int data) {
            this.data = data;
        }
    }

    public Node search(int data) {
        Node node = findNode(data);
        if (node.data == data) {
            return node;
        }

        return null;
    }

    // 插入结点
    public void insert(int data) {
        Node pre = findNode(data);
        if (pre.data == data) {
            // 插入的值已经存在，直接返回
            return;
        }

        // 双向链表中插入值
        Node cur = new Node(data);
        addListNode(pre, cur);

        // 插入值后，需要判断是否『晋升』，即插入节点上提
        Random random = new Random();
        int curLevel = 0;

        while (random.nextDouble() < PROMOTE_RATE) {
            if (curLevel == height) {
                addEmptyLevel();
            }

            while (pre.up == null) {
                pre = pre.left;
            }

            pre = pre.up;

            Node upper = new Node(data);
            addListNode(pre, upper);

            // 还得把 层与层 之间串起来
            cur.up = upper;
            upper.down = cur;

            // 别忘了这是个循环，如果还有第三层，也得把第三层和第二层串起来，所以cur节点也得上提
            cur = upper;

            curLevel++;
        }
    }

    // 删除结点
    public boolean remove(int data) {
        Node node = findNode(data);
        if (node == null) {
            return false;
        }

        // 删除当前节点，如果当前节点有上层，则递归删除
        int curLevel = 0;
        while (node != null) {
            node.left.right = node.right;
            node.right.left = node.left;

            // 如果删除当前节点后，当前层为空且当前层不为最底层，则还需要删除当前层
            if (curLevel != 0 && node.left.data == Integer.MIN_VALUE && node.right.data == Integer.MAX_VALUE) {
                removeLevel(node.left);
            } else {
                curLevel++;
            }

            node = node.up;
        }

        return true;
    }

    // 删除当前层
    private void removeLevel(Node left) {
        Node right = left.right;

        // 如果当前是最高层
        if (left.up == null) {
            head = left.down;
            tail = right.down;
            left.down.up = null;
            right.down.up = null;
        } else {
            // 不是最高层
            left.up.down = left.down;
            left.down.up = left.up;

            right.up.down = right.down;
            right.down.up = right.up;
        }

        height--;

    }

    private void addEmptyLevel() {
        height++;

        Node p1 = new Node(Integer.MIN_VALUE);
        Node p2 = new Node(Integer.MAX_VALUE);

        p1.right = p2;
        p2.left = p1;

        p1.down = head;
        p2.down = tail;

        head.up = p1;
        tail.up = p2;

        head = p1;
        tail = p2;
    }

    // 双向链表中插入值
    private void addListNode(Node pre, Node newNode) {
        newNode.left = pre;
        newNode.right = pre.right;
        pre.right.left = newNode;
        pre.right = newNode;
    }

    // 找到 <= data 值的节点
    private Node findNode(int data) {
        Node cur = head;

        while (true) {
            while (cur.right.data != Integer.MIN_VALUE && cur.right.data <= data) {
                cur = cur.right;
            }

            // 已经到底层了
            if (cur.down == null) {
                break;
            }

            cur = cur.down;
        }

        return cur;
    }
}